#include <iostream>
using namespace std;

//打印数组
void printArray(int array[], int n)
{
	for (int i = 0; i < n; i++)
	{
		cout << array[i] << " ";
	}
	cout << endl;
}

//插入排序函数定义
void insertion(int array[], int n)
{
	for (int i = 0; i < n; i++)
	{
		int j = i - 1;
		int temp = array[i];
		for (; j >= 0; j--)
		{
			if (array[j] < temp)
			{
				array[j + 1] = array[j];
			}
			else
				break;
		}
		array[j + 1] = temp;
	}
}

int bucketSort(int array[],int n,int k,int l)
{
	//找到最大最小值
	int max = array[n-1];
	int min = array[n - 1];
	for (size_t i = 0; i < n; i++)
	{
		if (array[i] > max)
		{
			max = array[i];
		}
		if (array[i] < min)
		{
			min = array[i];
		}
	}

	//定义二维数组桶
	int** buckets = new int* [k]();
	int* bucket = new int [k]();

	//定义桶的范围
	int bucketScope = int(floor(max - min) / k + 1);

	//为每个桶分配空间
	for (size_t s = 0; s < k; s++)
	{
		buckets[s] = new int[n]();
	}

	//将所有的元素放进桶里面
	for (size_t j = 0; j < n; j++)
	{
		int index = 0;
		index = int((array[j] - min) / bucketScope);
		buckets[index][bucket[index]++] = array[j];
	}

	//将桶里面的元素进行排序并拷贝出来
	int temp2 = 0;
	for (int i = k-1; i >=0; i--)
	{
		insertion(buckets[i], bucket[i]);
		for (int w = 0; w < bucket[i]; w++)
		{
			array[temp2++] = buckets[i][w];
		}
		delete[]buckets[i];
	}
	delete[] buckets;
	delete[] bucket;
	return array[l - 1];
}

int main()
{
	int array1[] = {22,46,56,66,75,35,57,90};
	int n = sizeof(array1) / sizeof(int);
	int k = 0;
	printArray(array1, n);
	cout << "What size do you want?" << endl;
	cin >> k;
	cout << "The anwser is:" <<bucketSort(array1,n,7,k)<< endl;
	printArray(array1, n);//打印排好序后的数组
}